Field of the Invention
The invention relates generally to the field of computer animation and, more specifically, to dynamic collision avoidance for crowd simulation over structured paths that intersect at waypoints.
Description of the Related Art
Crowd simulation is the process of simulating a crowd having a large number of animated characters placed in a computer-generated crowd area. For the characters in the crowd to appear realistic, crowd simulators typically provide algorithms that attempt to simulate movements of the characters in a realistic manner. Such movements include the characters in the crowd traversing pre-defined paths. Crowd simulators, however, do not account for characters in a crowd colliding with one another when traversing intersecting paths. Thus, as shown in FIG. 1, characters in a crowd simulation often collide with one another when traversing intersecting paths.
More specifically, FIG. 1 illustrates different frames of a crowd simulation animation 100, according to the prior art. Crowd simulation animation 100 includes frame 102, frame 104 and frame 106. Each frame includes two animated characters, referred to herein as “agents,” agent 108 and agent 110. Agent 108 is traversing path 112 and agent 110 is traversing path 114. Path 112 and path 114 intersect at intersection point 116. In frame 102 and frame 104, both agent 108 and agent 110 approach intersection point 114. The speeds at which agent 108 and agent 110 traverse path 112 and path 114 results in a collision of agent 108 and agent 110 at intersection point 116, as shown in frame 106.
Collisions between characters, such as the collision shown in FIG. 1, negatively impact the realism of the crowd simulation because humans, in real life, self-correct their motion to avoid these types of collisions. Therefore, simulations generated by a crowd simulator that do not account for collisions between the different characters in the simulations appear unrealistic.
As the foregoing illustrates, what is needed in the art is a technique that enables collisions between moving objects included in crowd simulation to be avoided.